import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2022-11-13
 * Time: 16:48
 */
public class Solution {
    public char[] arr;
    public String[] ret=new String[40320];
    public int count;

    public void dfs(int x){
        if(x==arr.length-1){
            //说明已经找到一种排列了
            ret[count++]=new String(arr);
            return ;
        }

        dfs(x+1);
        Set<Character> set=new HashSet<>();//防止交换时出现了相同字母表多次开头
        for(int i=x+1;i<arr.length;i++){
            char ch=arr[i];
            if(!set.contains(ch)){
                //没有开过头再交换
                set.add(ch);
                if(arr[x]==ch){
                    //相同直接跳过
                    continue;
                }
                //不相同再交换
                swap(x,i);
                dfs(x+1);
                //再换回来
                swap(x,i);
            }
        }

    }
    public void swap(int a,int b){
        char temp=arr[a];
        arr[a]=arr[b];
        arr[b]=temp;
    }
    public String[] permutation(String s) {
        arr=s.toCharArray();
        dfs(0);
        return Arrays.copyOf(ret,count);
    }
}
